//414. 第三大的数
//给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

#include <stdio.h>


void FastSort(int *a,int start,int end)
{
    int left = start;
    int right = end;
    int temp = a[left];
    if(left >= right)
        return;
    while(left < right)
    {
        while(left < right && a[right] < temp)
        {
            right--;
        }
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }
        while(left < right && a[left] > temp)
        {
            left++;
        }
        if(left < right)
        {
            a[right] = a[left];
            right--;
        }
    }
    a[left] = temp;
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}

int thirdMax(int* nums, int numsSize)
{
    FastSort(nums,0,numsSize-1);
    if(numsSize < 3)
    {
        return nums[0];
    }
    int first = nums[0];
    int second = 0;
    int third = 0;
    int j = 0;
    int k = 0;
    for(j = 1; j < numsSize; j++)
    {
        if(nums[j] < first)
        {
            second = nums[j];
            break;
        }
    }
    int flag = 0;
    for(k = j; k < numsSize; k++)
    {
        
        if(nums[k] < second)
        {
            flag = 1;
            third = nums[k];
            break;
        }
    }
    if(flag == 0)
        return nums[0];
    return third; 
}


int main()
{
    int a[10] = {84,84,26,348,23,4,2,3,4,23};
    printf("The third max number is %d\n",thirdMax(a,sizeof(a)/4));
    return 0;
}